0645. 错误的集合【简单】

• 1. 📝 题目描述
• 2. 🫧 评价
• 3. 🎯 s.1 - 使用哈希表统计
• 4. 🎯 s.2 - 数学
  • 4.1. 🧠 公式推导流程
• 5. 🎯 s.3 - 异或运算
• 6. 🤖 AI 点评
  • 6.1. ✅ 解法一：计数数组（哈希计数）
  • 6.2. ✅ 解法二：数学公式（和与平方和）
  • 6.3. ✅ 解法三：位运算（异或分组）
  • 6.4. 🔍 综合对比表
  • 6.5. ✅ 推荐结论
  • 6.6. 💡 附加建议

1. 📝 题目描述

• leetcode

集合 s 包含从 1 到 n 的整数。不幸的是，因为数据错误，导致集合里面某一个数字复制了成了集合里面的另外一个数字的值，导致集合 丢失了一个数字 并且 有一个数字重复。

给定一个数组 nums 代表了集合 S 发生错误后的结果。

请你找出重复出现的整数，再找到丢失的整数，将它们以数组的形式返回。

---

示例 1：

输入：nums = [1,2,2,4]
输出：[2,3]

示例 2：

输入：nums = [1,1]
输出：[1,2]

---

提示：

• 2 <= nums.length <= 10^4
• 1 <= nums[i] <= 10^4

2. 🫧 评价

• s.1 哈希表逻辑简单直接，易于理解；
• s.2 数学方法效率更高，但需要掌握一些基本的求和公式；
• s.3 利用数字的规律和异或位运算的特性来巧妙求解；
• 虽然 s.2、s.3 的空间复杂度都是 $O(1)$，比 s.1 的 $O(n)$ 更高，但从实际提交结果来看，s.1 表现会更好，这应该是因为提交时测试用例中给定的测试数据集比较特殊。
• 提交结果：

3. 🎯 s.1 - 使用哈希表统计

js

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findErrorNums = function (nums) {
  const n = nums.length
  const count = new Array(n + 1).fill(0)
  let duplicate = -1
  let missing = -1

  // 统计每个数字出现的次数
  for (const num of nums) {
    count[num]++
  }

  // 找到重复的数字和丢失的数字
  for (let i = 1; i <= n; i++) {
    if (count[i] === 2) {
      duplicate = i
    } else if (count[i] === 0) {
      missing = i
    }
  }

  return [duplicate, missing]
}

• 时间复杂度：$O(n)$，需要遍历数组两次，每次遍历都是线性时间
• 空间复杂度：$O(n)$，需要额外的数组来存储每个数字的出现次数

4. 🎯 s.2 - 数学

js

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findErrorNums = function (nums) {
  const n = nums.length
  let sum = 0 // 实际数组的和
  let squareSum = 0 // 实际数组的平方和
  let expectedSum = (n * (n + 1)) / 2 // 理论上数组的和
  let expectedSquareSum = (n * (n + 1) * (2 * n + 1)) / 6 // 理论上数组的平方和

  // 计算实际数组的和与平方和
  for (const num of nums) {
    sum += num
    squareSum += num * num
  }

  // diff = missing - duplicate
  let diff = expectedSum - sum
  // squareDiff = missing^2 - duplicate^2
  let squareDiff = expectedSquareSum - squareSum

  // missing + duplicate = squareDiff / diff
  let sumDiff = squareDiff / diff

  // 解方程得到结果
  let missing = (diff + sumDiff) / 2
  let duplicate = missing - diff

  return [duplicate, missing]
}

• 时间复杂度：$O(n)$，只需要遍历数组一次
• 空间复杂度：$O(1)$，只使用了常数个额外变量

4.1. 🧠 公式推导流程

• 基础计算：和与平方和
  • 首先我们定义几个关键值：
  • 实际数组的和：$\text{sum}=\sum nums$
  • 实际数组的平方和：$\text{squareSum}=\sum (num{s}_i^2)$
  • 理论正确数组的和：$\text{expectedSum}={\displaystyle \frac{n(n+1)}{2}}$
  • 理论正确数组的平方和：$\text{expectedSquareSum}={\displaystyle \frac{n(n+1)(2n+1)}{6}}$
• 差值计算
  • 基于题意，我们可以得出两个关键差值：
  • 和的差值：$\text{diff}=\text{expectedSum}-\text{sum}=missing-duplicate$
  • 平方和的差值：$\text{squareDiff}=\text{expectedSquareSum}-\text{squareSum}=missin{g}^2-duplicat{e}^2$
• 关键等式推导
  • 利用平方差公式：$missin{g}^2-duplicat{e}^2=(missing-duplicate)(missing+duplicate)$
  • 将已知条件代入：$\text{squareDiff}=\text{diff}\times (missing+duplicate)$
  • 因此可得：$missing+duplicate={\displaystyle \frac{\text{squareDiff}}{\text{diff}}}$
  • 记作：$\text{sumDiff}={\displaystyle \frac{\text{squareDiff}}{\text{diff}}}$
• 现在我们有两个方程：

$$\{\begin{array}{l}missing-duplicate=\text{diff}\\ missing+duplicate=\text{sumDiff}\end{array}$$

• 解这个方程组得到最终结果：
  • $missing={\displaystyle \frac{\text{diff}+\text{sumDiff}}{2}}$
  • $duplicate=missing-\text{diff}$

5. 🎯 s.3 - 异或运算

js

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var findErrorNums = function (nums) {
  const n = nums.length
  let xor = 0

  // 第一步：明确分组位
  // 遍历 nums，把所有元素依次异或到 xor 上
  for (const num of nums) {
    xor ^= num
  }

  // 遍历 1..n，把它们也依次异或到 xor 上
  for (let i = 1; i <= n; i++) {
    xor ^= i
  }
  // 此时成对出现的数字（正常的数字）会相互抵消，只剩下
  // xor = duplicate ^ missing

  // 找分组位
  // 因为 duplicate ≠ missing，所以 xor 至少有一位是 1，表示这两数在该位上不同。
  // 如果有多个 1 位，选哪一位都行，分组位 x 为 1 表示在 x 上 duplicate 和 missing 的值不同。
  // 这里选最右边的 1 位。
  const rightmostBit = xor & ~(xor - 1)

  // 第二步：根据分组位进行分组，明确两个候选
  // 利用 duplicate 和 missing 在 rightmostBit 位上不同来进行分组。
  // 组内其他正常数字，最终都会成对抵消，只剩下两个候选。

  // 组 1 分组位上是 1 ，组 2 分组位上是 0
  let xorGroup1 = 0
  let xorGroup2 = 0

  for (const num of nums) {
    if (num & rightmostBit) {
      xorGroup1 ^= num
    } else {
      xorGroup2 ^= num
    }
  }

  for (let i = 1; i <= n; i++) {
    if (i & rightmostBit) {
      xorGroup1 ^= i
    } else {
      xorGroup2 ^= i
    }
  }

  // 第三步：区分重复数和缺失数
  // 确定哪个是重复的数
  // 如果 xorGroup1 在数组中出现过，则它是重复的数，否则 xorGroup2 是重复的数
  for (const num of nums) {
    if (num === xorGroup1) {
      return [xorGroup1, xorGroup2]
    }
  }

  return [xorGroup2, xorGroup1]
}

• 时间复杂度：$O(n)$，需要遍历数组三次
• 空间复杂度：$O(1)$，只使用了常数个额外变量
• 算法思路：
  • 在 nums 与 1...n 组成的集合中：
    • 正常数字：出现两次
    • 重复数字：出现三次
    • 丢失数字：出现一次
  • 异或运算可以将重复的数字抵消，我们只需要找到一个分组的标准（duplicate 和 missing 任意一个不同的位），不断的进行异或，最后就能定位到两个结果 xorGroup1、xorGroup2，这两个结果中必有一个是丢失的数字，另一个是重复的数字。
  • 最后判断哪个在 nums 中出现，这个数字就是重复的数字，另一个就是丢失的数字。
• 相同解法的例题：260. 只出现一次的数字 III

6. 🤖 AI 点评

Qwen3-Max

这三段代码都实现了 LeetCode 645. 错误的集合（Find the Duplicate and Missing Number） 的功能：给定一个长度为 n 的数组 nums，其中包含从 1 到 n 的整数，但有一个数字重复了，另一个数字缺失了。要求返回 [重复的数字, 缺失的数字]。

下面我们从 时间复杂度、空间复杂度、可读性、数值稳定性、适用场景 等维度对三种解法进行详细对比：

---

6.1. ✅ 解法一：计数数组（哈希计数）

// 使用 count 数组统计频次

• ✔ 优点：
  • 逻辑清晰，易于理解：直接统计每个数字出现次数，再遍历找重复（count=2）和缺失（count=0）。
  • 时间复杂度：O(n)，两次遍历。
  • 空间复杂度：O(n)，需要额外长度为 n+1 的数组。
  • 数值稳定：不涉及大数运算，不会溢出（在 JS 中数字是浮点，但小整数安全）。
  • 适用于所有语言，包括对整数溢出敏感的语言（如 C++、Java）。
• ❌ 缺点：
  • 额外使用 O(n) 空间，不是最优空间解法。
  • 如果 n 极大（如 10⁷），可能内存压力较大（但在 JS 中通常可接受）。
• 📌 适用场景：
  • 面试中首选（清晰、鲁棒、易写）。
  • 对空间要求不苛刻时的最佳实践。

---

6.2. ✅ 解法二：数学公式（和与平方和）

// 利用 sum 和 sum of squares 建立方程

• ✔ 优点：
  • 空间复杂度 O(1)，只用几个变量。
  • 时间复杂度 O(n)，一次遍历。
  • 巧妙利用数学性质，体现算法思维。
• ❌ 缺点：
  • 数值溢出风险：虽然 JS 使用 IEEE 754 双精度浮点数，能安全表示整数到 2^53 - 1，但当 n 很大时（如 n > 10⁶），n³ 级别的 expectedSquareSum 可能超出安全整数范围，导致精度丢失。
    • 例如：n = 10^5 → n³ ≈ 10^15，仍在安全范围内（Number.MAX_SAFE_INTEGER ≈ 9e15）。
    • 但 n = 10^6 → n³ = 1e18，超出安全整数范围，结果可能错误。
  • 可读性较差：需要理解平方和公式和代数推导。
  • 调试困难：若结果错误，难以定位是逻辑问题还是精度问题。
• 📌 适用场景：
  • 空间极度受限，且 n 较小（如 n < 10⁵）。
  • 算法竞赛中追求 O(1) 空间时可考虑（但需注意溢出）。

---

6.3. ✅ 解法三：位运算（异或分组）

// 利用 XOR 找出 duplicate ^ missing，再分组

• ✔ 优点：
  • 空间复杂度 O(1)。
  • 时间复杂度 O(n)。
  • 无溢出风险：纯位运算，适合大数。
  • 非常巧妙，体现位运算技巧。
• ❌ 缺点：
  • 逻辑复杂，难理解：需要理解异或性质、分组思想。
  • 代码较长，易出错：分组、判断重复数需额外遍历。
  • 最后仍需一次遍历确认哪个是重复数（不能仅靠值大小判断）。
  • 实际性能未必优于解法一：现代 CPU 对数组访问优化很好，而位运算优势在底层语言更明显。
• 📌 适用场景：
  • 面试中展示位运算能力（但需能清晰解释）。
  • 禁止使用额外空间且不能有精度风险的极端场景。

---

6.4. 🔍 综合对比表

维度	解法一（计数）	解法二（数学）	解法三（位运算）
时间复杂度	O(n)	O(n)	O(n)
空间复杂度	O(n)	O(1)	O(1)
可读性	⭐⭐⭐⭐⭐（极佳）	⭐⭐（需数学推导）	⭐⭐（位运算较晦涩）
数值稳定性	⭐⭐⭐⭐⭐（无风险）	⭐（大 n 时可能溢出/精度丢失）	⭐⭐⭐⭐⭐（无风险）
实现难度	简单	中等	较难
面试推荐度	⭐⭐⭐⭐⭐	⭐⭐	⭐⭐⭐（若能讲清楚）
生产代码适用	✅ 高	❌（有精度隐患）	⚠️（可读性差）

---

6.5. ✅ 推荐结论

• 日常开发 / 面试首选：解法一（计数数组）
  理由：清晰、安全、高效、易维护。空间换时间在大多数场景下是值得的。
• 若面试官明确要求 O(1) 空间：
  • 先尝试 解法三（位运算），并能清晰解释原理。
  • 若担心讲不清，可提 解法二，但要主动指出 “当 n 很大时可能存在精度问题，在 JS 中需谨慎”，展现工程意识。
• 避免在生产环境使用解法二，除非你 100% 确定 n 足够小。

---

6.6. 💡 附加建议

在 JavaScript 中，由于数字是浮点类型，解法二的“整数除法”看似没问题，但一旦超出 Number.MAX_SAFE_INTEGER（≈9e15），(diff + sumDiff) / 2 可能不是整数，导致返回浮点数（如 2.000000000000001），进而被判定错误。

而解法一和解法三始终返回精确整数。

---

✅ 总结一句话：

“能用简单方法解决的问题，就不要用复杂方法。”
—— 除非题目明确限制空间或考察特定技巧。